class Solution {
    public:
        int numDecodings(string s) {
            int n = s.size();
            vector<int> dp(n);
            if(n == 1){
                if(s[0] <= '9'&&s[0] >= '1' )   return 1;
                else return 0;
            }
            if(n == 2){
                int num = 0;
                if(s[0] <='9'&&s[0] >= '1'&&s[1] <='9'&&s[1] >= '1') num++;
                if(((s[0]-'0')*10 + (s[1]-'0')) <=26 &&((s[0]-'0')*10 + (s[1]-'0'))>=10) num++;
                return num;
            }
            if(s[0] <= '9'&&s[0] >= '1' )   dp[0] = 1;
            else dp[0] = 0;
            int nu = 0;
            if(s[0] <='9'&&s[0] >= '1'&&s[1] <='9'&&s[1] >= '1') nu++;
            if(((s[0]-'0')*10 + (s[1]-'0')) <=26 &&((s[0]-'0')*10 + (s[1]-'0'))>=10) nu++;
            dp[1] = nu;
            for(int i = 2 ; i < n ; i++){
                dp[i] = 0;
                if(s[i] <= '9'&&s[i] >= '1' )   dp[i] +=dp[i-1];
                if(((s[i-1]-'0')*10 + (s[i]-'0')) <=26 &&((s[i-1]-'0')*10 + (s[i]-'0'))>=10) dp[i] +=dp[i-2];
            }
            return dp[n-1];
        }
    };

    //改进
    class Solution {
        public:
            int numDecodings(string s) {
                int n = s.size();
                vector<int> dp(n,0);
                //初始化
                if(s[0] != '0') dp[0] = 1;
                if(n == 1)  return dp[0];
                int t = (s[0]-'0')*10+s[1]-'0';
                if(t >=10 && t<=26)  dp[1]++;
                if(s[0] != '0' && s[1] != '0')  dp[1]++;
                //
                for(int i = 2; i < n ; i++){
                    if(s[i] != '0' ) dp[i] +=dp[i-1];
        
                    int t = (s[i-1]-'0')*10+s[i]-'0';
                    if(t >=10 && t<=26)  dp[i]+= dp[i-2];
                }
                return dp[n-1];
        
            }
        };